package com.dyw.Day28;

/**
 * @author Devil
 * @create 2022-02-22 15:02
 *
 * 买卖股票的最佳时机
 * 给定一个数组 prices ，它的第i 个元素prices[i] 表示一支给定股票第 i 天的价格。
 *
 * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
 *
 * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0
 *
 * 思路: 有题可知 我们在一个时间点买股票 在另一个时间点买股票 找到能满足最大利润的两点 并返回最后的利润
 * 方法一: 双指针法 满指针指向目前最小的价格点 该点就为我们买入股票的点 然后快指针继续走 每一步就要更新最小的价格点 和最大利润点 并计算
 * 并且更新当前的最大利润 知道最后
 */
public class Demo01 {
    public int maxProfit(int[] prices) {
        if(prices.length==0||prices==null){
            return 0;
        }
        int maxPro = 0;//记录最大的利润
        int min = prices[0];//记录最小利润
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min,prices[i]);
            maxPro = Math.max(prices[i]-min,maxPro);
        }
        return maxPro;
    }
    public int maxProfit2(int[] prices){
        if(prices==null||prices.length==0){
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        //dp[i][0] 标识第i+1天没持有股票的利润 dp[i][1]标识第i+1天持有股票的利润
        //边界条件
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
        }
        //最后返回手中没有股票的结果(即卖出的利润)
        return dp[length-1][0];
    }
    public int maxProfit3(int[] prices){
        if(prices==null||prices.length==0){
            return 0;
        }
        int length = prices.length;
        //第一天
        int noHold = 0;
        int hold = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            //递推公式
            noHold = Math.max(noHold,hold+prices[i]);
            hold = Math.max(hold,-prices[i]);
        }
        return noHold;
    }
}
